<!doctype html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>数组中的第 K 个最大元素 - 算法详解</title>
    <link href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css" rel="stylesheet">
    <link href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css" rel="stylesheet">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
        }
        .serif-font {
            font-family: 'Noto Serif SC', serif;
        }
        .gradient-text {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
            -webkit-background-clip: text;
            -webkit-text-fill-color: transparent;
            background-clip: text;
        }
        .hero-gradient {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
        }
        .card-hover {
            transition: all 0.3s ease;
        }
        .card-hover:hover {
            transform: translateY(-5px);
            box-shadow: 0 20px 40px rgba(0,0,0,0.1);
        }
        .code-block {
            background: #1e1e1e;
            border-radius: 12px;
            overflow: hidden;
        }
        .code-header {
            background: #2d2d2d;
            padding: 10px 20px;
            display: flex;
            align-items: center;
            justify-content: space-between;
        }
        .code-dots {
            display: flex;
            gap: 8px;
        }
        .dot {
            width: 12px;
            height: 12px;
            border-radius: 50%;
        }
        .dot-red { background: #ff5f56; }
        .dot-yellow { background: #ffbd2e; }
        .dot-green { background: #27c93f; }
        pre {
            margin: 0;
            padding: 20px;
            overflow-x: auto;
        }
        code {
            font-family: 'Consolas', 'Monaco', monospace;
            color: #d4d4d4;
            line-height: 1.6;
        }
        .keyword { color: #c586c0; }
        .function { color: #dcdcaa; }
        .string { color: #ce9178; }
        .number { color: #b5cea8; }
        .comment { color: #6a9955; }
        .operator { color: #d4d4d4; }
        .builtin { color: #4ec9b0; }
        @keyframes float {
            0%, 100% { transform: translateY(0px); }
            50% { transform: translateY(-20px); }
        }
        .float-animation {
            animation: float 6s ease-in-out infinite;
        }
        .drop-cap {
            float: left;
            font-size: 4rem;
            line-height: 1;
            font-weight: 700;
            margin-right: 0.5rem;
            margin-top: -0.2rem;
            color: #667eea;
        }
        .mermaid {
            display: flex;
            justify-content: center;
            margin: 2rem 0;
        }
    </style>
</head>
<body class="bg-gray-50">
    <!-- Hero Section -->
    <section class="hero-gradient text-white py-20 px-6">
        <div class="max-w-6xl mx-auto">
            <div class="text-center">
                <div class="mb-6">
                    <i class="fas fa-layer-group text-6xl opacity-80 float-animation"></i>
                </div>
                <h1 class="text-5xl md:text-6xl font-bold mb-6 serif-font">
                    数组中的第 K 个最大元素
                </h1>
                <p class="text-xl md:text-2xl opacity-90 max-w-3xl mx-auto leading-relaxed">
                    探索高效寻找数组中第 K 大元素的算法艺术
                </p>
                <div class="mt-10 flex justify-center gap-6">
                    <div class="bg-white bg-opacity-20 rounded-lg px-6 py-3 backdrop-blur-sm">
                        <i class="fas fa-clock mr-2"></i>
                        <span>时间复杂度 O(n log k)</span>
                    </div>
                    <div class="bg-white bg-opacity-20 rounded-lg px-6 py-3 backdrop-blur-sm">
                        <i class="fas fa-microchip mr-2"></i>
                        <span>空间复杂度 O(k)</span>
                    </div>
                </div>
            </div>
        </div>
    </section>

    <!-- Main Content -->
    <main class="max-w-6xl mx-auto px-6 py-16">
        <!-- Problem Description -->
        <section class="mb-16">
            <div class="bg-white rounded-2xl shadow-lg p-8 md:p-12 card-hover">
                <h2 class="text-3xl font-bold mb-6 flex items-center">
                    <i class="fas fa-question-circle text-purple-600 mr-3"></i>
                    <span class="gradient-text">题目描述</span>
                </h2>
                <p class="text-lg leading-relaxed text-gray-700">
                    <span class="drop-cap serif-font">给</span>定一个未排序的整数数组，找到其中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大元素，而不是第 k 个不同的元素。这是一道经典的算法题目，考察对数据结构和算法的灵活运用。
                </p>
            </div>
        </section>

        <!-- Core Concepts -->
        <section class="mb-16">
            <div class="grid md:grid-cols-2 gap-8">
                <div class="bg-white rounded-2xl shadow-lg p-8 card-hover">
                    <div class="text-center mb-6">
                        <i class="fas fa-mountain text-5xl text-indigo-600"></i>
                    </div>
                    <h3 class="text-2xl font-bold mb-4 text-center">堆方法</h3>
                    <p class="text-gray-700 leading-relaxed">
                        维护一个大小为 k 的最小堆，遍历数组时不断更新堆中元素，最终堆顶即为第 k 大元素。
                    </p>
                    <div class="mt-6 bg-indigo-50 rounded-lg p-4">
                        <p class="text-sm text-indigo-700">
                            <i class="fas fa-info-circle mr-2"></i>
                            适合处理数据流和大规模数据
                        </p>
                    </div>
                </div>
                <div class="bg-white rounded-2xl shadow-lg p-8 card-hover">
                    <div class="text-center mb-6">
                        <i class="fas fa-bolt text-5xl text-purple-600"></i>
                    </div>
                    <h3 class="text-2xl font-bold mb-4 text-center">快速选择法</h3>
                    <p class="text-gray-700 leading-relaxed">
                        基于快速排序的分区思想，通过不断缩小搜索范围，快速定位第 k 大的元素位置。
                    </p>
                    <div class="mt-6 bg-purple-50 rounded-lg p-4">
                        <p class="text-sm text-purple-700">
                            <i class="fas fa-info-circle mr-2"></i>
                            平均性能最优，原地操作节省空间
                        </p>
                    </div>
                </div>
            </div>
        </section>

        <!-- Algorithm Visualization -->
        <section class="mb-16">
            <div class="bg-white rounded-2xl shadow-lg p-8 md:p-12">
                <h2 class="text-3xl font-bold mb-8 text-center">
                    <i class="fas fa-project-diagram text-purple-600 mr-3"></i>
                    算法流程图
                </h2>
                <div class="mermaid">
                    graph TD
                        A[开始] --> B{选择算法}
                        B -->|堆方法| C[创建大小为k的最小堆]
                        B -->|快速选择| D[选择基准元素]
                        C --> E[遍历数组元素]
                        E --> F{元素 > 堆顶?}
                        F -->|是| G[替换堆顶并调整]
                        F -->|否| E
                        G --> E
                        E -->|遍历完成| H[返回堆顶元素]
                        D --> I[分区操作]
                        I --> J{基准位置 = k-1?}
                        J -->|是| K[返回基准元素]
                        J -->|否| L{基准位置 > k-1?}
                        L -->|是| M[在左侧继续查找]
                        L -->|否| N[在右侧继续查找]
                        M --> D
                        N --> D
                        H --> O[结束]
                        K --> O
                        
                        style A fill:#667eea,stroke:#fff,stroke-width:2px,color:#fff
                        style O fill:#764ba2,stroke:#fff,stroke-width:2px,color:#fff
                        style B fill:#f3f4f6,stroke:#667eea,stroke-width:2px
                        style J fill:#f3f4f6,stroke:#764ba2,stroke-width:2px
                </div>
            </div>
        </section>

        <!-- Complexity Analysis -->
        <section class="mb-16">
            <h2 class="text-3xl font-bold mb-8 text-center">
                <span class="gradient-text">复杂度分析</span>
            </h2>
            <div class="grid md:grid-cols-2 gap-8">
                <div class="bg-gradient-to-br from-indigo-500 to-purple-600 rounded-2xl p-8 text-white">
                    <h3 class="text-2xl font-bold mb-6 flex items-center">
                        <i class="fas fa-layer-group mr-3"></i>
                        堆方法
                    </h3>
                    <div class="space-y-4">
                        <div class="bg-white bg-opacity-20 rounded-lg p-4 backdrop-blur-sm">
                            <p class="font-semibold mb-1">时间复杂度</p>
                            <p class="text-2xl">O(n log k)</p>
                        </div>
                        <div class="bg-white bg-opacity-20 rounded-lg p-4 backdrop-blur-sm">
                            <p class="font-semibold mb-1">空间复杂度</p>
                            <p class="text-2xl">O(k)</p>
                        </div>
                    </div>
                </div>
                <div class="bg-gradient-to-br from-purple-500 to-pink-600 rounded-2xl p-8 text-white">
                    <h3 class="text-2xl font-bold mb-6 flex items-center">
                        <i class="fas fa-bolt mr-3"></i>
                        快速选择法
                    </h3>
                    <div class="space-y-4">
                        <div class="bg-white bg-opacity-20 rounded-lg p-4 backdrop-blur-sm">
                            <p class="font-semibold mb-1">平均时间复杂度</p>
                            <p class="text-2xl">O(n)</p>
                        </div>
                        <div class="bg-white bg-opacity-20 rounded-lg p-4 backdrop-blur-sm">
                            <p class="font-semibold mb-1">空间复杂度</p>
                            <p class="text-2xl">O(1)</p>
                        </div>
                    </div>
                </div>
            </div>
        </section>

        <!-- Code Implementation -->
        <section class="mb-16">
            <h2 class="text-3xl font-bold mb-8 text-center">
                <i class="fas fa-code text-purple-600 mr-3"></i>
                <span class="gradient-text">代码实现</span>
            </h2>
            <div class="code-block">
                <div class="code-header">
                    <div class="code-dots">
                        <div class="dot dot-red"></div>
                        <div class="dot dot-yellow"></div>
                        <div class="dot dot-green"></div>
                    </div>
                    <span class="text-gray-400 text-sm">Python</span>
                </div>
                <pre><code><span class="keyword">def</span> <span class="function">findKthLargest</span>(nums, k):
    <span class="keyword">from</span> heapq <span class="keyword">import</span> heappush, heappop
    heap = []
    <span class="keyword">for</span> num <span class="keyword">in</span> nums:
        <span class="builtin">heappush</span>(heap, num)
        <span class="keyword">if</span> <span class="builtin">len</span>(heap) <span class="operator">></span> k:
            <span class="builtin">heappop</span>(heap)
    <span class="keyword">return</span> heap[<span class="number">0</span>]</code></pre>
            </div>
        </section>

        <!-- Key Insights -->
        <section class="mb-16">
            <div class="bg-gradient-to-r from-purple-50 to-indigo-50 rounded-2xl p-8 md:p-12">
                <h2 class="text-3xl font-bold mb-8 text-center">
                    <i class="fas fa-lightbulb text-yellow-500 mr-3"></i>
                    核心要点
                </h2>
                <div class="grid md:grid-cols-3 gap